星尘

18. 四数之和

发表于 更新于 分类于

18. 四数之和

题目

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1:

1
2
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2:

1
2
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

题解

15.三数之和 的双指针解法是一层 for 循环 num[i] 为确定值，然后循环内有 left 和 right 下表作为双指针，找到 nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层 for 循环 nums[k] + nums[i] 为确定值，依然是循环内有 left 和 right 下表作为双指针，找出 nums[k] + nums[i] + nums[left] + nums[right] == target 的情况，三数之和的时间复杂度是 O(n^2)，四数之和的时间复杂度是O(n^3) 。

那么一样的道理，五数之和、六数之和等等都采用这种解法。

对于15.三数之和双指针法就是将原本暴力 O(n^3) 的解法，降为 O(n^2) 的解法，四数之和的双指针解法就是将原本暴力 O(n^4) 的解法，降为 O(n^3) 的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # 四数之和只是在三数之和的基础上在增加一层循环
        result = []

        # 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 4，返回 []
        if len(nums) < 4:
            return []

        size = len(nums)
        nums.sort()

        for i, v in enumerate(nums):
            # 判断当前值是否和上一位值是否重复，重复的就跳过，目的是为了去除重复解
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            for k in range(i + 1, size):
                if k > i + 1 and nums[k] == nums[k - 1]:
                    continue

                left = k + 1
                right = size - 1

                # 只要左指针没有超过右指针，那么就一直循环
                while left < right:
                    sum_value = v + nums[left] + nums[right] + nums[k]
                    if sum_value > target:
                        # 和值大于 target, 右指针需要左移
                        right -= 1
                    elif sum_value < target:
                        # 和值小于 target, 左指针需要右移
                        left += 1
                    else:
                        result.append([v, nums[left], nums[right], nums[k]])
                        # 判断左边界和右边界是否和下一位值重复，目的是为了去除重复解
                        while left != right and nums[left] == nums[left + 1]:
                            left += 1
                        while left != right and nums[right] == nums[right - 1]:
                            right -= 1
                        # 最后左右指针各移动一步
                        right -= 1
                        left += 1
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func fourSum(nums []int, target int) [][]int {
	var result [][]int

	if len(nums) < 4{
		return result
	}

	size := len(nums)
	sort.Ints(nums)

	for i, v:= range nums{
		if i > 0 && nums[i] == nums[i-1]{
			continue
		}

		for k := i + 1; k < size; k++ {
			if k > i+1 && nums[k] == nums[k-1] {
				continue
			}

			left := k +1
			right := size - 1

			for left < right{
				sumValue := v + nums[left] + nums[right] + nums[k]
				if sumValue > target{
					right -=1
				}else if sumValue < target {
					left += 1
				}else{
					result = append(result, []int{v, nums[left], nums[right], nums[k]})

					for left != right && nums[left] == nums[left+1]{
						left += 1
					}
					for left != right && nums[right] == nums[right-1]{
						right -=1
					}
					left +=1
					right -=1
				}
			}
		}
	}
	return result
}

变体

总结

参考